CS-04 : DATA STRUCTURE THROUGH 'C' & PASCAL  DEC 1997

NOTE: Question 1 is compulsory. Attempt any three from the rest.  Algorithms should be written near to C or Pascal language statements.

1. (a)  Implement a C- language program recursively to test for a palindrome.  A palindrome is an
         alphanumeric string such that the string reads the same in a forward and backward direction.
    (b) (i) Write a C-language implementation for sequentially mapping multiple queues.
         (ii) Write a C-language implementation for adding an item to the multiple queues.
    (c) Suggest an efficient implementation of many to many relation shown in the following table:
 

 A  X   in the table indicates a course-opted by a student e.g. s5  has taken  CS-04 and CS-06.  Assume that association table such as shown above may be quite sparse.

2. Write a C- Program to add two polynomials.

3 (a) Draw the internal memory representation of the following binary tree using
   (i)  linked list
   (ii) threaded binary tree representation

    (b) Write a C- Program to find out inorder sequence of a Threaded Binary Tree.
4. (a)  for the following diagraph, obtain

5. Consider the following tree:  

(a)  Draw an equivalent Binary tree of the above general tree.
(b)  Write a C- Program Equal (P,Q) which returns 1 if Bianry tree pointed to by P and Q have the
      same structure and the same information at corresponding nodes and 0 otherwise.

6.  Explain briefly using a simple example, the logic of Quicksort algorithm.  Write a non recursive
     algorithm for Quicksort and show how Quicksort would sort the array containing 4,3,1,6,7,2,5,8.